Skip to main content

Merge K Sorted Lists

Intro to K-way Merge​

  • Source
  • K-way Merge helps you solve problems that involve a set of sorted arrays.
  • Whenever you’re given ‘K’ sorted arrays, you can use a Heap to efficiently perform a sorted traversal of all the elements of all arrays.
  • You can push the smallest element of each array in a Min Heap to get the overall minimum. After getting the overall minimum, push the next element from the same array to the heap. Then, repeat this process to make a sorted traversal of all elements.
  • The steps involved to solve this kind of problem will be
    • Insert the first element of each array in a Min Heap.
    • After this, take out the smallest (top) element from the heap and add it to the merged list.
    • After removing the smallest element from the heap, insert the next element of the same list into the heap.
    • Repeat steps 2 and 3 to populate the merged list in sorted order.
l1 = [2,6,8]
l2 = [3,6,7]
l3 = [1,3,4]

q = PriorityQueue()
q.put([l1[0],0, a])
q.put([l2[0],0, b])
q.put([l3[0],0, c])

res = []
while not q.empty():
	elt, index, arr = q.get()
	res.append(elt)

	if index != len(arr)-1:
		index += 1
		q.put([a[index], index, arr])
return res